package com.ross.test;

import java.util.Arrays;

/**
 * @version 1.0.0
 * @className: ApiTestSort
 * @description: 归并排序
 * @author: zhangjunfa
 * @date: 2023/4/13 10:12
 */
public class ApiTestMergeSort {
    public static void main(String[] args) {
        int[] b = {49, 38, 65, 97, 76, 13, 27, 50};
        msort(b, 0, b.length - 1);

        System.out.println(Arrays.toString(b));
        // 结果：[13, 27, 38, 49, 50, 65, 76, 97]
    }

    static void msort(int[] a, int start, int end) {
        int mid = (start + end) >> 1; /*取数组中间点，平分数组*/
        if (start < end) {
            msort(a, start, mid);      /*递归将a[start,mid]归并*/
            msort(a, mid + 1, end);   /*递归将a[mid+1,end]归并*/
            mergeSort(a, start, mid, end); /*将数组的[start,mid]和[mid+1,end]合并成一个数组t[]*/

        }
    }

    static void mergeSort(int[] a, int start, int mid, int end) {
        int[] t = new int[end - start + 1];/*每次合并要新建一个大小为被合并数组的总和的数组*/
        int i = start, j = mid + 1, k = 0;
        while (i <= mid && j <= end) { /*将a[]中start~mid,和mid+1~end梳子按照有小到大归并入t[];*/
            if (a[i] < a[j]) {
                t[k++] = a[i++];
            } else {
                t[k++] = a[j++];
            }
        }
        while (i <= mid) {       /* 将剩余的i~mid的数字一次添加到t[]中*/
            t[k++] = a[i++];
        }
        while (j <= end) {       /* 将剩余的j~end的数字一次添加到t[]中*/
            t[k++] = a[j++];
        }
        for (int p : t) {            /*最后将合并后的t[]更新到数组a[]的start~end部分*/
            a[start++] = p;
        }
    }
}
